//算法效率分析未二种：第一种是"时间效率">>>第二种是"空间效率"
//算法中的基本操作(循环)的执行次数，为算法的"时间复杂度"
//"空间复杂度"是一个算法在运行过程中"临时占用存储空间大小的量度"

//大O渐进表示法：计算时间复杂度时，不需要计算精准的执行次数，只需要"大概执行次数"!!!
//大O符号>>>O()：用于描述函数渐进行为的数学符号
//推导大O渐进方法：1.用常数1取代运行时间中的所有加法常数(执行次数为常数都为O(1))
// 2.在修改后的运行次数函数中，最保留最高阶(N ^ 常数 + N + 10只保留N ^ 常数)
// 3.如果最高阶项存在且不是1，则去掉与这个项目相乘的常数(常数 * N)
#include <iostream>
#include <cstring>
#include <cassert>
using namespace std;

//这里时间复杂度为：O(N^2) ->去掉了对结果影响不大的项(2N和常数项)
void Func1(int N)
{
    // Func1执行的基本操作次数:"F(N) = N^2 + 2 * N + 10
    // N = 10 >>> F(N) = 130
    // N = 100 >>> F(N) = 10210
    // N = 1000 >>> F(N) = 1002010
    int count = 0;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            ++count;
        }
    }
    for (int k = 0; k < 2 * N; ++k)
    {
        ++count;
    }
    int M = 10;
    while (M--)
    {
        ++count;
    }
    cout << count << endl;
}

//这里时间复杂度为：O(1) ->执行次数为"常数都使用1取代所有加法的常数"
// F(N) = 100
void Func2(int N)
{
    int count = 0;
    for (int k = 0; k < 100; ++k)
    {
        ++count;
    }
    printf("%d\n", count);
}

//实例3基本操作执行了M+N次，有两个未知数M和N，时间复杂度为 O(N+M)
void Func3(int N, int M)
{
    int count = 0;
    for (int k = 0; k < M; ++k)
    {
        ++count;
    }
    for (int k = 0; k < N; ++k)
    {
        ++count;
    }
}

//这里时间复杂度："分最好最坏和折中情况" ->时间复杂度一般看最坏
//最好情况为：O(1) ->直接找到子字符
//最坏情况为：O(N) ->没有找到，全部遍历一次
//折中情况为：O(N/2)
const char *strchr(const char *str, char character)
{
    while (*str != '\0')
    {
        if (*str == character)
            return str;
        ++str;
    }
    return NULL;
}

//基本操作执行最好1次，最坏O(logN)次，时间复杂度为 O(logN) >>> ps：logN在算法分析
//中表示是底数为2，对数为N。有些地方会写成lgN（建议通过折纸查找的方式讲解logN是怎么计算出来的）
//有些书上为lgN，也是表示long以2为底，对数为N
int BinarySearch(int *a, int n, int x)
{
    //二分查找 -> 缺点为"需要升序数组"
    assert(a);
    int begin = 0;
    int end = n;
    while (begin < end)
    {
        int mid = begin + ((end - begin) >> 1);
        if (a[mid] < x)
            begin = mid + 1;
        else if (a[mid] > x)
            end = mid;
        else
            return mid;
    }
    return -1;
}

//实例7通过计算分析发现基本操作"递归了N次"，时间复杂度为O(N)
// n的阶层->n * n-1 * n-2...*1
long long Factorial(size_t N)
{
    return N < 2 ? N : Factorial(N - 1) * N;
}

int main()
{
    system("pause");
    return 0;
}